The invention is related to systems for detecting synchronization errors.
Data are recorded on magnetic disks in tracks that are separated into sectors. Many sectors include, respectively, a header portion that lists the sector number and other information, and a data portion in which the data are recorded. Other sectors include the data portions, but not the headers. Synchronization information is included between the sectors, so that a disk drive can determine the start of the individual sectors and ultimately the start of the data portions of the respective sectors. The drive then, as necessary, counts sectors after reading a header to arrive at the designated sector to be written to or read.
Before recording, the data are typically encoded into data code words using an is error correction code (ECC). The data code word is then recorded in the data portion of the sector. To later read the data, a disk drive moves a read/write head over the appropriate track and, using the recorded synchronization information, determines the start of the data portion of the sector of interest. The head then reads the data code word and supplies it to a decoder. The decoder reproduces the data by manipulating the code word symbols and, as necessary, correcting any errors using the ECC.
If the drive makes a mistake in determining the location of the start of the data code word, that is, if there is a synchronization error, the drive reads a portion of the data code word and either information that precedes the data code word or information that follows the data code word, depending on the direction of the synchronization error. If the decoder mistakenly interprets what is read from the disk as a valid data code word, the decoder then xe2x80x9ccorrectsxe2x80x9d what it perceives as errors in the code word, and sends the result as error-free data to an application or a user.
The ECCs that are most often used are Reed-Solomon codes. The Reed-Solomon codes encode the data over a Galois Field (2q) where xe2x80x9cqxe2x80x9d is the number of bits in a code symbol or element. The Reed-Solomon codes are cyclic. Accordingly, if c0c1 . . . cc is an unshortened code word, where the cj are elements of GF(2p), c1 . . . ccc0 is also a code word, as is ccc0c1 . . . cc-1. This means that a synchronization error of one or more symbols may produce a different, but valid code word. If the mis-synchronization involves a number of bits rather than full symbols, the decoder most likely detects that every code word symbol is in error, assuming the code word includes a relatively large number of redundancy symbols. The decoder thus cannot correct the errors, and labels the data as erroneous.
To protect against the misinterpretation of the symbol-sized synchronization errors, a certain prior system adds a noise-like sequence into each data code word before the code word is recorded. Using Galois Field operations, the addition is accomplished by XOR""ing the sequence and the data code word. Before decoding, the system removes the sequence from the retrieved code word by XOR""ing the sequence to the code word. If the read operation is synchronized to the start of the codeword, that is, if there is no synchronization error, the XOR""ing of the sequence and the retrieved code word reproduces the original data code word.
Otherwise, the XOR""ing of the sequence to the retrieved code word introduces errors into the code word. Assuming the sequence is properly chosen such that the XOR""ing of the sequence with a shifted, or misaligned, version of the sequence does not result in a valid codeword, the decoder detects more errors in the decoded code word than the ECC can correct. The decoder then labels the mis-synchronized data as erroneous. If the sequence is not properly chosen and the XOR""ing operation instead produces a different and valid code word, the decoder xe2x80x9ccorrectsxe2x80x9d the errors using the ECC.
The prior system uses a trial and error approach to finding the noise-like sequence. The trial and error approach is time consuming and does not necessarily produce a sequence that introduces a maximum number of errors into a retrieved code word which contains synchronization errors. Further, the prior systems have to store the selected sequence in the encoder and also in the decoder, which increases the overall storage requirements of the system. Accordingly, the mis-synchronization technique may be impractical for systems that have limited storage capacities.
An error correction system that solves certain of these problems produces a code word for recording by XOR""ing to a data code word, which is encoded in accordance with a distance d Reed-Solomon code, a coset leader that is a code word of a distance dxe2x80x2 super code, but not a code word of the distance d code. When the code word is retrieved, the system XOR""s it with the coset leader. If there is no synchronization error, the second XOR""ing operation removes the coset leader from the code word, to reproduce the data code word. If there is a synchronization error, the XOR""ing operation ensures that the retrieved code word includes a term that is a Hamming distance of dxe2x80x2 from every valid code word of the distance d Reed-Solomon code. The system then decodes the result in a conventional manner, and as long as dxe2x80x2 greater than d/2 the system detects more errors than the ECC can correct.
The prior system determines appropriate distance dxe2x80x2 super codes from which to select the coset leader based on the generator polynomial of the distance d Reed-Solomon code. The system then selects from one of these codes a coset leader b(x) that is not also a code word of the distance d code. Next, the system tests that the term j(x)=b(x)*xs+b(x) is not a valid code word of the distance d code for every S of interest, where xe2x88x92Txe2x89xa6S less than T and T is the maximum number of symbols by which the read/write head may be misaligned. If j(x) is a valid code word of the distance d code, the system selects and tests each of the remaining coset leaders from the distance dxe2x80x2 codes. If none of the coset leaders are appropriate, the system selects and tests the coset leaders from distance dxe2x80x3=dxe2x80x2xe2x88x921 Reed-Solomon codes, and an appropriate coset leader in the distance dxe2x80x3 code can generally be found.
To reduce the associated storage requirements, the system may select a coset leader to be a code word that contains several versions of a shortened code word of the distance dxe2x80x2 code. The system then stores only the shortened code word, and essentially reproduces the coset leader by XORing the shortened code word to the data code word a number of times. Alternatively, the system may generate the coset leader from the stored shortened code word using, for example, a dedicated shift register.
The prior system thus provides a mechanism to select a coset leader for use in mis-synchronization detection and a way to reduce associated storage requirements. As discussed below, I have developed a system that provides a mechanism for including in a code word for recording a coset leader that has optimum mis-synchronization detection properties for the associated code. Further, the system minimizes storage requirements, while at the same time eliminating the need for dedicated hardware to reproduce the coset leader.
The inventive system is an error correction system constructed in accordance with a distance d Reed-Soloman code that, during a modified step in the encoding operation, includes in a code word for recording a coset leader of a distance dxe2x88x921 code. The modified encoding step includes in an appropriate manner in the encoding operation a predetermined non-zero xe2x80x9ccoset symbolxe2x80x9d that results in the encoder producing a modified set of R redundancy symbols. The result of the encoding is a code word that includes in the redundancy symbols a coset leader that is a hamming distance dxe2x88x921 from every valid code word of the distance d code. As discussed in more detail below, the modified encoding step ensures that the included coset leader is a code word of a distance dxe2x88x921 code, and thus, optimum for detecting synchronization errors in the code words. Further, the modified encoding step eliminates the need to XOR a coset leader to a data code word in a separate step after the encoding operation has produced the data code word.
During decoding, the system decodes the recorded code word and generates associated error syndromes. In a last decoding step, the system removes the effects of the included coset leader from the syndromes, by including a predetermined syndrome value associated with the coset leader. If there is no synchronization error and the code word is error-free, the result is a set of all zero syndromes. If there are d/2 or fewer code word errors but no synchronization error, the system produces a non-zero syndrome pattern that is associated with a correctable number of errors. However, if there is a synchronization error, the inclusion of the predetermined syndrome value produces a syndrome pattern that is associated with an uncorrectable number of errors.
The error correction system stores only the coset symbol and the associated syndrome value, and thus, the storage requirements are minimal. Further, the system may be constructed by modifying a combined encoding/syndrome generating circuit, as discussed in more detail below. This is in contrast to systems that must either store the entire coset leader or include an additional encoder or dedicated shift register to generate the coset leader from, for example, a stored shortened code word.